package com.cn.codebrush.数组.双指针;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author Boolean
 * @Date 2022/5/30 22:34
 * @Version 1.0
 */
public class No287寻找重复数 {
    public static void main(String[] args) {
        int[] nums = {1,3,4,2,2};
        System.out.println(findDuplicate2(nums));
    }


    /**
     * 解法三
     * @param nums
     * @return
     */
    public int findDuplicate3(int[] nums) {
        int n = nums.length;
        Map map = new HashMap<>();
        for(int i=0;i<n;i++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i],nums[i]);
            }else {
                return nums[i];
            }
        }

        return nums[0];
    }

    /**
     * 解法二
     * @param nums
     * @return
     */
    public static int findDuplicate2(int[] nums) {
        /**
         快慢指针思想, fast 和 slow 是指针, nums[slow] 表示取指针对应的元素
         注意 nums 数组中的数字都是在 1 到 n 之间的(在数组中进行游走不会越界),
         因为有重复数字的出现, 所以这个游走必然是成环的, 环的入口就是重复的元素,
         即按照寻找链表环入口的思路来做
         **/
        int fast = 0, slow = 0;
        while(true) {
            fast = nums[nums[fast]];
            slow = nums[slow];
            if(slow == fast) {
                //为什么fast归0？当跑这么多步数，fast和slow相遇，fast比slow多走一倍。如果fast置0，此时slow比fast多的刚好是相遇时fast比slow多走的步数，两者一起起跑，
                // 再走相同的步数刚好相遇。
                //**
                //想了很久很久才明白为什么找到一次重合之后要把fast清零然后同步走。终于想明白了！找到重合位置之后，因为此时的slow与fast位于同一位置，
                // 而fast比slow多走了一倍的距离，说明slow(从0到目前的位置)走的距离与fast多走的距离（从目前的位置沿着环绕N圈）长度一致，且中间一定有环的部分重合。
                // 那么一个从0走，一个从重合位置走，他们一定会同时到达环的起点。

                fast = 0;
                while(nums[slow] != nums[fast]) {
                    fast = nums[fast];
                    slow = nums[slow];
                }
                return nums[slow];
            }
        }
    }


    /**
     * 解法一
     * @param nums
     * @return
     */
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);

        for(int i=1;i<nums.length;i++){
            if(nums[i] == nums[i-1]){
                return nums[i];
            }
        }

        return nums[0];
    }
}
